6.25 We can perform buildHeap in linear time for leftist heaps by considering each element as a one-node leftist heap, placing all these heaps on a queue, and performing the following step: Until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result. a. Prove that this algorithm is O(N) in the worst case. b. Why might this algorithm be preferable to the algorithm described in the text? - | |
| View Solution | |
| << Back | Next >> |